import java.net.Inet4Address;
import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {

    public int halfQuestions(int[] questions) {
        int[] arr=new int[1001];
        for(int i : questions){
            arr[i]++;
        }
        Arrays.sort(arr);
        int n=questions.length/2;
        int count=0;
        for(int i=arr.length-1;i>=0;i--){
            count++;
            n-=arr[i];
            if(n<=0){
                break;
            }
        }
        return count;
    }




    public List<Integer> luckyNumbers (int[][] matrix) {
        int row=matrix.length;
        int col=matrix[0].length;
        List<Integer> list=new ArrayList<>();
        for(int i=0;i<row;i++){
            int min=matrix[i][0];
            int k=0;
            for(int j=1;j<col;j++){
                if(matrix[i][j]<min){
                    min=matrix[i][j];
                    k=j;
                }
            }
            int x=0;
            for(;x<row;x++){
                if(matrix[x][k]>min){
                    break;
                }
            }
            if(x==row){
                list.add(min);
            }
        }
        return list;
    }










    public String sortSentence(String s) {
        Map<Integer,String> map=new HashMap<>();
        String[] arr=s.split(" ");
        for(String str : arr){
            int key=Integer.parseInt(str.substring(str.length()-1));
            map.put(key,str.substring(0,str.length()-1));
        }
        StringBuilder sb=new StringBuilder();
        for(int i=1;i<=map.size();i++){
            sb.append(map.get(i));
            sb.append(" ");
        }
        return sb.toString().trim();
    }












    public int numOfStrings(String[] patterns, String word) {
        int count=0;
        for(String s : patterns){
            if(word.contains(s)){
                count++;
            }
        }
        return count;
    }












    public int uniqueMorseRepresentations(String[] words) {
        String[] str=new String[]{".-","-...","-.-.","-..",".","..-.","--.",
                "....","..",".---","-.-",".-..","--","-.",
                "---",".--.","--.-",".-.","...","-","..-",
                "...-",".--","-..-","-.--","--.."};
        Set<String> set=new HashSet<>();
        for(String s : words){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<s.length();i++){
                char ch=s.charAt(i);
                sb.append(str[ch-'a']);
            }
            set.add(sb.toString());
        }
        return set.size();
    }











    public boolean areOccurrencesEqual(String s) {
        Map<Character,Integer> map=new HashMap<>();
        int index=0;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.get(ch)!=null){
                map.put(ch,map.get(ch)+1);
            }else{
                map.put(ch,0);
            }
            index=map.get(ch);
        }
        for(Map.Entry<Character,Integer> entry : map.entrySet()){
            if(index!= entry.getValue()){
                return false;
            }
        }
        return true;
    }








    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=countNodess(root.left);
        int right=countNodess(root.right);
        if(left==right){
            return countNodes(root.right)+(1<<left);
        }else{
            return countNodes(root.left)+(1<<right);
        }
    }
    public int countNodess(TreeNode root){
        int count=0;
        while(root!=null){
            root= root.left;
            count++;
        }
        return count;
    }





    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,ArrayList<String>> map=new HashMap<String,ArrayList<String>>();
        for(String s : strs){
            char[] ch=s.toCharArray();
            Arrays.sort(ch);
            String str=new String(ch);
            ArrayList<String> tmp=map.getOrDefault(str,new ArrayList<>());
            tmp.add(s);
            map.put(str,tmp);
        }
        return new ArrayList<List<String>>(map.values());
    }








    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        int ret=root.val;
        if(root!=null){
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(i==0){
                        ret=tmp.val;
                    }
                    if(tmp.left!=null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.offer(tmp.right);
                    }
                }
            }
        }
        return ret;
    }








    public ListNode[] listOfDepth(TreeNode tree) {
        List<ListNode> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if(tree!=null){
            queue.offer(tree);
            while(!queue.isEmpty()){
                ListNode tmp=new ListNode(0);
                ListNode cur=tmp;
                int size=queue.size();
                for(int i=0;i<size;i++){
                    TreeNode root=queue.poll();
                    cur.next=new ListNode(root.val);
                    if(root.left!=null){
                        queue.offer(root.left);
                    }
                    if(root.right!=null){
                        queue.offer(root.right);
                    }
                    cur=cur.next;
                }
                list.add(tmp.next);
                tmp.next=null;
            }
        }
        return list.toArray(new ListNode[]{});
    }
}
